package leetcode.code0990;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public boolean equationsPossible(String[] equations) {
		Map<Integer, Integer> map = new HashMap<>();
		for (String equ : equations) {
			if (equ.charAt(1) == '=') {
				union(map, equ.charAt(0), equ.charAt(3));
			}
		}
		for (String equ : equations) {
			if (equ.charAt(1) == '!') {
				if (isSameSet(map, equ.charAt(0), equ.charAt(3))) {
					return false;
				}
			}
		}
		return true;
	}

	private boolean isSameSet(Map<Integer, Integer> map, int a, int b) {
		int pa = p(map, a);
		int pb = p(map, b);
		return pa == pb;
	}

	private void union(Map<Integer, Integer> map, int a, int b) {
		int pa = p(map, a);
		int pb = p(map, b);
		if (pa != pb) {
			map.put(pa, pb);
		}
	}

	private int p(Map<Integer, Integer> map, int a) {
		if (!map.containsKey(a)) {
			map.put(a, a);
		}
		if (map.get(a) != a) {
			map.put(a, this.p(map, map.get(a)));
		}
		return map.get(a);
	}

	public void union(int[] p, int a, int b) {
		p[find(p, a)] = find(p, b);
	}

	public int find(int[] p, int id) {
		if (p[id] != id) {
			p[id] = this.find(p, p[id]);
		}
		return p[id];
	}

	int[] p;

	public void init(int size) {
		p = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
	}

	public void union(int a, int b) {
		p[find(a)] = find(b);
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	@Override
	public void debug4() {
		H.compare(false,
				this.equationsPossible(H.str2array2("[\"f==a\",\"a==b\",\"f!=e\",\"a==c\",\"b==e\",\"c==f\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int[] p = new int[10];
		for (int i = 0; i < 10; i++) {
			p[i] = i;
		}
		so.union(p, 4, 7);
		so.union(p, 7, 8);
		so.union(p, 8, 9);
		H.print(p);
		int ans = so.find(p, 1);
		H.print(p);
		System.out.println(ans);
		ans = so.find(p, 4);
		H.print(p);
		System.out.println(ans);

	}

}
